package ali;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存
 * @author wxh
 */
public class LRUCache {

	private Map<Integer, DLinkedNode> cache;
	private int size; // 实时标记当前LRU缓存容量大小
	private int capacity; // 用户设定的容量
	private DLinkedNode head, tail;

	public LRUCache(int capacity) {
		this.cache = new HashMap(capacity);
		this.size = 0;
		this.capacity = capacity;
		// 使用伪头部和伪尾部节点
		head = new DLinkedNode();
		tail = new DLinkedNode();
		head.next = tail;
		tail.prev = head;
	}

	public int get(int key) {
		// 1、先通过哈希表定位取值
		DLinkedNode node = cache.get(key);
		if (node == null) {
			return -1;
		}
		// 2、如果存在，将当前元素移到双向链表队列的头部
		moveToHead(node);
		return node.value;
	}

	public void put(int key, int value) {
		DLinkedNode node = cache.get(key);
		if (node == null) {
			// 如果 key 不存在，创建一个新的节点
			DLinkedNode newNode = new DLinkedNode(key, value);
			// 添加进哈希表
			cache.put(key, newNode);
			// 添加至双向链表的头部
			addToHead(newNode);

			++size;
			if (size > capacity) {
				// 如果超出容量，删除双向链表的尾部节点
				DLinkedNode tail = removeTail();
				// 删除哈希表中对应的项
				cache.remove(tail.key);
				--size;
			}
		} else {
			// 更新 value
			node.value = value;
			// 移到头部
			moveToHead(node);
		}
	}

	// 移动node到头节点
	private void moveToHead(DLinkedNode node) {
		//1、从双向链表中，删除当前节点
		removeNode(node);
		//2、将当前节点插入到双向链表的头部
		addToHead(node);
	}

	// 添加node到头节点
	private void addToHead(DLinkedNode node) {
		node.prev = head;
		node.next = head.next;
		head.next.prev = node;
		head.next = node;
	}

	// 移除node节点
	private void removeNode(DLinkedNode node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
	}

	// 移除尾结点
	private DLinkedNode removeTail() {
		DLinkedNode node = tail.prev;
		removeNode(node);
		return node;
	}

	class DLinkedNode {
		int key;
		int value;
		DLinkedNode prev;
		DLinkedNode next;
		public DLinkedNode() {}
		public DLinkedNode(int key, int value) {
			this.key = key;
			this.value = value;
		}
	}

}